%0 Conference Proceedings
%4 sid.inpe.br/sibgrapi@80/2006/07.21.07.13
%2 sid.inpe.br/sibgrapi@80/2006/07.21.07.13.06
%@doi 10.1109/SIBGRAPI.2006.41
%T Single Triangle Strip and Loop on Manifolds with Boundaries
%D 2006
%A Diaz-Gutierrez, Pablo,
%A Eppstein, David,
%A Gopi, M.,
%@affiliation University of California, Irvine
%@affiliation University of California, Irvine
%@affiliation University of California, Irvine
%E Oliveira Neto, Manuel Menezes de,
%E Carceroni, Rodrigo Lima,
%B Brazilian Symposium on Computer Graphics and Image Processing, 19 (SIBGRAPI)
%C Manaus, AM, Brazil
%8 8-11 Oct. 2006
%I IEEE Computer Society
%J Los Alamitos
%S Proceedings
%K Hamiltonian Cycle, Perfect Matching, Triangle Strip.
%X The single triangle-strip loop generation algorithm on a triangulatedtwo-manifold presented by Gopi and Eppstein cite{GE:04} is based onthe guaranteed existence of a perfect matching in its dualgraph. However, such a perfect matching is not guaranteed in the dualgraph of triangulated manifolds with boundaries. In this paper, wepresent algorithms that suitably modify the results of the dual graphmatching to generate a single strip loop on manifolds withboundaries. Further, the algorithm presented in cite{GE:04} canproduce only strip loops, but not linear strips. We present an algorithmthat does topological surgery to construct linear strips, withuser-specified start and end triangles, on manifolds with or withoutboundaries. The main contributions of this paper include graphalgorithms to handle unmatched triangles, reduction of the number ofSteiner vertices introduced to create strip loops, and finally a novelmethod to generate single linear strips with arbitrary start and endpositions.
%@language en
%3 diazgutierrez-SingleTriangleStrip.pdf